//
// Description: 105. 从前序与中序遍历序列构造二叉树
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    int n = preorder.size();
    // 定义哈希表，快速定位前序序列节点在中序序列的位置
    unordered_map<int, int> index;
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i;
    }

    function<TreeNode *(int, int, int, int)> buildTreeInternal = [&](int pre_left, int pre_right, int in_left,
                                                                     int in_right) -> TreeNode * {
        if (pre_right < pre_left || in_right < in_left) {
            return nullptr;
        }
        auto root = new TreeNode(preorder[pre_left]);
        int mid = index[preorder[pre_left]];
        int len = mid - in_left;
        root->left = buildTreeInternal(pre_left + 1, pre_left + len, in_left, mid - 1);
        root->right = buildTreeInternal(pre_left + 1 + len, pre_right, mid + 1, in_right);

        return root;
    };

    return buildTreeInternal(0, n - 1, 0, n - 1);
}

int main() {
    vector<int> preorder{3, 9, 20, 15, 7};
    vector<int> inorder{9, 3, 15, 20, 7};
    auto root = buildTree(preorder, inorder);
    cout << printfTreeNodeOfLevel(root) << endl;

    return 0;
}